Cryptographic algorithms are widely used for encryption of messages, authentication, encryption signatures and identification. The well-known DES (Data Encryption Standard) has been in use for a long time, and was updated by Triple-DES, which has been replaced in many applications by the AES (Advanced Encryption Standard). AES is an approved encryption standard by the U.S. government. AES is a substitution permutation network. AES is fast enough to execute in both computer software and hardware implementations, relatively easy to implement, and requires little memory space.
FIG. 1 provides a conceptual illustration of an example cryptographic operation 100 using AES. As shown in FIG. 1, input data 140 is processed in an initial round 110, nine middle rounds 120, and a final round 130. After all of the rounds are completed, output state 150 will be produced. When operation 100 is a decryption operation, input data 140 will be cipher text (e.g., encrypted data) and output state 150 will be plain text (e.g., unencrypted data). When operation 100 is an encryption operation, input data 140 can be either cipher text or plain text, and output state 150 will be cipher text (if the input data 140 is cipher text, then the output state 150 will be twice ciphered). Input data 140 can be any computer readable message. For instance, input data 140 could be an encrypted content file, video content, image content, audio content, a computer message, a secure transmission, or any other string of values that can be encoded as bits.
AES has a fixed block size of 128 bits and a key size of 128, 192 or 256 bits. Due to the fixed block size of 128 bits, AES operates on a 4×4 array of bytes (e.g., 16 bytes). Accordingly, input data 140 will always be a 16 byte array of information. Input data 140 can be a sub-portion of a larger message. For instance, a three megabyte audio file can be divided into 16 byte portions and each portion encrypted according to operation 100. During the operations of AES, the input data 140 will be referred to as “AES state”. AES state is a 16-byte buffer upon which the AES operations are performed.
AES uses key expansion and like most block ciphers a set of encryption and decryption rounds (iterations). Each round involves similar processes. As shown in FIG. 1, initial round 110, nine middle rounds 120, and final round 130 each contain similar operations (e.g., SubBytes, ShiftRows, MixColumns, and AddRoundKey). The entire AES algorithm (e.g., operation 100) contains 11 AddRoundKey operations, 10 SubBytes operations, 10 ShiftRows operations, and 9 MixColumns operations. Preliminarily to operation 100, the original 16 byte cipher key 155 is expanded to 11 subkeys, during what is called the key-scheduling operation. The 11 subkeys include subkey 0 160, subkeys 1-9 165, and subkey 10 170. The 11 subkeys are each used in different rounds of operation 100. Each subkey is 16 bytes long.
Initial round 110 shows operation 100 receiving input data 140 and performing AddRoundKey operation 115. AddRoundKey operation 115 performs a logical exclusive disjunction operation (hereinafter “XOR”) on subkey 0 155 and input data 140. The XOR operation combines input data 140 with subkey 0 155.
Following the initial round 110, operation 100 performs nine middle rounds 120. Each of the nine middle rounds 120 include four operations: SubBytes 121, ShiftRows 120, MixColumns 123, and AddRoundKey 124. SubBytes 121 substitutes the bytes of the current AES state according to a substitution table. This substitution table is sometimes referred to as a substitution box or “SBOX” table. This operation provides non-linearity in the cipher.
ShiftRows 122 cyclically shifts bytes in each row of the AES state by certain offsets. As the AES state is a 4×4 16 byte array, the AES state can be arranged in a 4 row, 4 column arrangement. ShiftRows 122 will shift different rows of the 4×4 AES state by different amounts. For instance, the first row is left unchanged. Each byte of the second row is shifted one to the left. Similarly, the third and fourth rows are shifted by offsets of two and three respectively.
MixColumns 123 combines bytes of the AES state from each column using an invertible linear transformation. MixColumns 123 takes four bytes as input and outputs four bytes, where each input byte affects all four output bytes. MixColumns may be implemented via a table lookup operation. Together with ShiftRows, MixColumns provides diffusion in the cipher.
AddRoundKey 124 combines a round key from subkeys 1-9 165 with the AES state. For each round, a subkey is derived from cipher key 155. Each subkey is the same size as the AES state (e.g., a 4×4 16 byte array). The subkey is combined with the AES state using an XOR operation.
After AddRoundKey 124, the operation 100 then performs additional rounds until only one additional subkey remains (e.g., nine rounds). Once the nine middle rounds 120 are completed, operation 100 performs a final round 130 of operations. The final round 130 includes: SubBytes 131, ShiftRows 132, and AddRoundKey 133. These final operations are the same as those described above in connection with the earlier rounds. Final subkey 10 170 is combined with the AES state to produce output state 140.
The previous description of operation 100 corresponded to the order of operations required to encrypt content. Decryptions operations under AES are substantially similar, but the order of operations is reversed and inverses of the operations are used. The inverse of AddRoundKey is AddRoundKey itself. The inverse of SubBytes is Inverse SubBytes, which is another table look up operation. The inverse of MixColumns is Inverse MixColumns, which is another lookup operation. The inverse of ShiftRows is Inverse ShiftRows, which is another move from one byte location to another. Different versions of AES (e.g., the 256-bit variant) can include different numbers of rounds and different state sizes. For further detail on AES, see the specification for the ADVANCED ENCRYPTION STANDARD (AES), NIST, http://csrc.nist.gov/publications/fips/fips197/fips−197.pdf.
Of note, arithmetic implementations of AES do not provide much security against an attacker recovering a secret key, if the attacker has privileged access to the system implementing the cipher. However, AES is often used in potentially insecure environments. For instance, AES could be employed in a white box environment. In a white box model, it is presumed that an attacker has total access to the system performing an encryption, including being able to observe directly a state of memory, program execution, and so on. In such a model, an encryption key can be observed in or extracted from memory, and so ways to conceal operations indicative of a secret key are important. For example, the attacker can learn the secret key of an AES software implementation by observing the execution of the Key Schedule algorithm.
DRM applications are one instance where it's desired to keep the attacker from finding the secret key even though the attacker has complete control of the execution process. Chow et. al. (Stanley Chow, Philip A. Eisen, Harold Johnson, Paul C. van Oorschot: White-Box Cryptography and an AES Implementation. Selected Areas in Cryptography 2002: 250-270) give a construction of the AES algorithm for such white box model. The security of this construction resides in the use of table lookups and masked data. The input and output mask applied to this data is never removed along the process. In this solution, there is a need for knowing the key value at the compilation time, or at least to be able to derive the tables from the original key in a secure environment.
However, this solution does not solve all the application's needs for block cipher's encryption. Indeed, the case where the key is derived through a given process and then unknown at the compilation time is not included. One typical use-case is when a program is distributed over several users and each of them has their own key. In this case, it is impossible to disseminate different code to each user from a practical point of view. Another use-case is just when generating session keys (different for each session) through a given process. Of course, in this case the key is unknown at compilation time. A last case is when it is necessary to store a plenty of keys. However, it is not reasonable to consider storing around 700 kB for each key.